//https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/
class Solution {
public:
    int fib(int n) {
        if (n == 0)
            return 0;
        if (n <= 2)
        {
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = a + b;

        int cnt = 2;
        while (cnt < n)
        {
            c = a + b;
            a = b;
            b = c % 1000000007;

            ++cnt;
        }

        return c % 1000000007;
    }
};